Next greater element III

Time: O(LogN) = O(1); Space: O(LogN) = O(1)

Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n.

If no such positive 32-bit integer exists, you need to return -1.

Example 1:

Input: 12

Output: 21

Example 2:

Input: 21

Output: -1

[5]:

class Solution1(object):
    def nextGreaterElement(self, n):
        """
        :type n: int
        :rtype: int
        """
        digits = list(map(int, list(str(n))))
        k, l = -1, 0
        for i in range(len(digits) - 1):
            if digits[i] < digits[i + 1]:
                k = i

        if k == -1:
            digits.reverse()
            return -1

        for i in range(k + 1, len(digits)):
            if digits[i] > digits[k]:
                l = i

        digits[k], digits[l] = digits[l], digits[k]
        digits[k + 1:] = digits[:k:-1]

        result = int("".join(list(map(str, digits))))

        return -1 if result >= 0x7FFFFFFF else result

[6]:

s = Solution1()
n = 12
assert s.nextGreaterElement(n) == 21
n = 21
assert s.nextGreaterElement(n) == -1